package com.xcc.dataStructures.leetcode;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * 注意:
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * <p>
 * 示例 1:
 * 输入: [1, 5, 11, 5]
 * 输出: true
 * <p>
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 * <p>
 * 链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo006_PartitionEqualSubsetSum {

    public static void main(String[] args) {
//        int[] nums = {1, 5, 11, 5};
        int[] nums = {1, 2, 3, 4};
        Demo006_PartitionEqualSubsetSum subsetSum = new Demo006_PartitionEqualSubsetSum();
        System.out.println(subsetSum.canPartition(nums));
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //如果集合的和不为偶数直接返回false
        if (sum % 2 != 0) {
            return false;
        }
        return knapsack(nums, sum / 2);
    }

    /**
     * 使用动态规划背包问题解决
     *
     * @param nums 对应的重量w和价值v均为nums
     * @param c    背包的容量
     * @return 如果最后背包的总价值(重量)不等于c 则false
     */
    private boolean knapsack(int[] nums, int c) {
        int[][] dp = new int[nums.length ][c + 1];
        //初始化第一行
        for (int j = 0; j <= c; j++) {
            dp[0][j] = nums[0] > j ? 0 : nums[0];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= c; j++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], nums[i - 1] + dp[i - 1][j - nums[i - 1]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        show(dp);
        return dp[nums.length - 1][c] == c;
    }

    private void show(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
